#include<string>
#include<vector>
#include<random>
/*泛型接口，发出多个散列函数*/
template <typename AnyType>
class MyCuckooHashFamily
{
public:
    /*哈希函数*/
    size_t hash(const AnyType & x, int which) const
    /*查看哈希函数的数量*/
    int getNumberOfFunctions ();
    /*构建新的哈希函数*/
    void generateNewFunctions ();
};

/*泛型接口的显式具体化*/
template <int count>
class StringHashFamily
{
private:
    /*存储哈希函数列参数*/
    vector<int> MULTIPLIERS;
    /*用来给哈希函数列参数赋值的随机向量*/
    UniformRandom r;
public:
    StringHashFamily() : MULTIPLIERS(count) { generateNewFunctions(); }

    int getNumberOfFunctions() const { return count; }
    /*用随机数r给参数列赋值*/
    void generateNewFunctions()
    {
        for(auto & mult: MULTIPLIERS)
            mult = r.nextInt();
    }
    /*哈希函数列的构造函数*/
    size_t hash(const string & x, int which) const
    {
        /*每个哈希函数用不同的参数和相同的公式*/
        const int multiplier = MULTIPLIERS[which];
        /*哈希值*/
        size_t hashVal = 0;
        /*每个哈希函数利用ASCII法构造*/
        for(auto ch : x)
            hashVal = multiplier * hashVal + ch;
        return hashVal;
    }
};

/*杜鹃散列*/
template <typename AnyType, typename HashFamily>
class CuckooHashTable
{
private:
    /*带序号的桶元素*/
    struct HashEntry
    {
        AnyType element;
        bool isActive;

        HashEntry(const AnyType & e = AnyType(), bool a = false) : element {e} , isActive {a} {}
        HashEntry(AnyType && e, bool a = false) : element {std::move(e)}, isActive{a} {}
    };
    /*哈希值向量（一个桶里只装一个，若冲突则重建哈希表）*/
    vector<HashEntry> array;
    /*哈希表项数总数量*/
    int currentSize;
    /*哈希函数的数量（哈希表数量）*/
    int numHashFunctions;
    /*记录再散列次数*/
    int rehashes;
    /*泛型具体化时再定义*/
    UniformRandom r;
    HashFamily hashFunctions;
    /*最大装填因子*/
    static const double MAX_LOAD = 0.40;
    /*扩张的次数*/
    static const int ALLOWED_REHASHES = 5;

    bool isActive (int currentPos) const { return isActive; }
    
    /*该定义写在类的外部*/
    bool insertHelper1 (const AnyType & xx)
    bool insertHelper1 (AnyType && xx)
    

    /*选取适当的哈希函数，并换算成数组下标*/
    size_t myHash (const AnyType & x, int which) const
    { return hashFunctions.hash(x, which) % array.size(); } //哈希函数没有具体化
    /*查阅哈希函数，返回包含x的下标。没找到则返回-1（很直观的操作）*/
    int findPos (const AnyType & x) const
    {
        for (int i = 0; i < numHashFunctions; ++i)
        {
            int pos = myHash(x,i);
            if(isActive(pos) && array[pos].element == x)
                return pos;
        }
        return -1;
    }
    /*哈希表的扩张：使用重建函数*/
    void expand()
    { rehash( static_cast<int>(array.size()) / MAX_LOAD ); }
    /* 互递归：rehash和insert相互调用。其中insert是主力
     * 
     * 
    */
    void rehash() //刷新参数表，散列表数量和尺寸不变
    {
        hashFunctions.generateNewFunctions();
        rehash(array.size());
    }
    /*和探测散列相同，只是一个封装，不同的主要是insertHelp1*/
    void rehash(int newSize)
    {
        vector<HashEntry> oldArray = array;
        array.resize(nextPrime(newSize)); //保持哈希表长度为素数
        for(auto & entry : array)
            entry.isActive = false;
        currentSize = 0;
        for(auto & entry: oldArray)
            if(entry.isActive)
                insert(std::move(entry.element));
    }

public:
    explicit CuckooHashTable(int size = 101) : array(nextPrime(size))
    {
        numHashFunctions = hashFunctions.getNumberOfFunctions();
        rehashes = 0;
        makeEmpty();
    }

    void makeEmpty()
    {
        currentSize = 0;
        for (auto & entry : array)
            entry.isActive = false;
    }
    bool contains(const AnyType & x) const
    { return findPos(x) != -1; }
    bool remove(const AnyType & x)
    {
        int currentPos = findPos(x);
        if (!isActive(currentPos))
            return false;
        array[currentPos].isActive = false;
        --currentSize;
        return true;
    }
    /*插入函数的包装，最后要调用实现函数insertHelper1*/
    bool insert(const AnyType & x)
    {
        if(contains(x))
            return false;
        if(currentSize >= array.size() * MAX_LOAD)
            expand();
        return insertHelper1(x);
    }
    bool insert (AnyType && x)
};

/*insert和rehash的互调用*/
template <typename AnyType, typename HashFamily>
bool CuckooHashTable <AnyType, HashFamily> ::insertHelper1(const AnyType & xx)
{
    /*最大循环次数*/
    const int COUNT_LIMIT = 100;
    AnyType x = xx;
    
    /*无尽的查找-重建循环，直到符合return条件（存在空位）为止*/
    while (true)
    {
        /*最后一个和x冲突的值的索引（初始为无冲突，即-1）*/
        int lastPos = -1;
        int pos;
        /*在各个散列表中查找，找到则插入，找不到则随机逐出一项*/
        for(int count = 0; count < COUNT_LIMIT; ++count)
        {
            /*若找到空位则插入*/
            for (int i = 0; i<numHashFunctions; ++i)
            {
                pos = myHash(x,i);

                if(!isActive(pos))
                {
                    array[pos] = std::move(HashEntry{std::move(x),true});
                    ++currentSize;
                    return true;
                }
            }
            
            /*若遍历哈希表也找不到空位，则逐出一个随机项（重新选一个函数列参数）*/

            int i = 0;  //i仅在循环作用域内生效，所以可以再次声明
            //随机选取一项作为被逐出项
            do pos = myHash(x,r.nextInt(numHashFunctions));
            //因为每次while循环都重新选择一个哈希函数，所以为了防止两个哈希函数都探测到相同位置的被逐出项后，分别用自己的项覆盖它造成死循环。所以设置循环上限为一个奇数5
            while (pos == lastPos && i++ < 5);

            
            lastPos = pos; //更新最后被逐出项的位置
            std::swap(x,array[pos].element); //因为x是不受保护的地址，所以相当于用x覆盖了pos位置的数据项（逐出）
        }
        /* 查找循环失败并逐出项后
         * 首先进行重建哈希表
         * 如果重建次数过多，则不如扩张哈希表
         * 
        */
        if(++rehashes > ALLOWED_REHASHES)
        {
            expand();
            rehashes = 0;
        }
        else
            rehash();
    }
}